package com.leetcode.algorithm.y22.m09.w2;

import java.util.ArrayList;
import java.util.Arrays;
import java.util.HashSet;
import java.util.LinkedList;
import java.util.List;
import java.util.Queue;
import java.util.Set;

/**
 * 417. 太平洋大西洋水流问题
 * 
 * https://leetcode.cn/problems/pacific-atlantic-water-flow/
 * 
 * @author jie.deng
 *
 */
class Question0417Solution01 {

	public List<List<Integer>> pacificAtlantic(int[][] heights) {
		int m = heights.length;
		int n = heights[0].length;
		List<List<Integer>> result = new ArrayList<>();

		Set<Integer> pacificSet = new HashSet<>();
		for (int col = 0; col < n; col++) {
			// 第一行
			pacificSet.add(col);
		}
		for (int row = 0; row < m; row++) {
			// 第一列
			pacificSet.add(row * n);
		}
		Set<Integer> visitedSet = new HashSet<>();
		Queue<Integer> queue = new LinkedList<>();
		queue.addAll(pacificSet);
		visitedSet.addAll(pacificSet);
		while (!queue.isEmpty()) {
			int size = queue.size();
			int[][] dirs = new int[][] { { 0, 1 }, { 1, 0 }, { 0, -1 }, { -1, 0 } };
			for (int i = 0; i < size; i++) {
				int idx = queue.poll().intValue();
				int r = idx / n;
				int c = idx % n;
				for (int[] dir : dirs) {
					int row = r + dir[0];
					int col = c + dir[1];
					if (row >= 0 && row < m && col >= 0 && col < n && heights[row][col] >= heights[r][c]) {
						int i2 = row * n + col;
						if (visitedSet.add(i2)) {
							if (pacificSet.add(i2)) {
								queue.offer(i2);
							}
						}
					}
				}
			}
		}

		Set<Integer> atlanticSet = new HashSet<>();
		for (int col = 0; col < n; col++) {
			// 倒数一行
			atlanticSet.add((m - 1) * n + col);
		}
		for (int row = 0; row < m; row++) {
			// 倒数一列
			atlanticSet.add(row * n + n - 1);
		}
		visitedSet.clear();
		queue.clear();
		queue.addAll(atlanticSet);
		visitedSet.addAll(atlanticSet);
		while (!queue.isEmpty()) {
			int size = queue.size();
			int[][] dirs = new int[][] { { 0, 1 }, { 1, 0 }, { 0, -1 }, { -1, 0 } };
			for (int i = 0; i < size; i++) {
				int idx = queue.poll().intValue();
				int r = idx / n;
				int c = idx % n;
				for (int[] dir : dirs) {
					int row = r + dir[0];
					int col = c + dir[1];
					if (row >= 0 && row < m && col >= 0 && col < n && heights[row][col] >= heights[r][c]) {
						int i2 = row * n + col;
						if (visitedSet.add(i2)) {
							if (atlanticSet.add(i2)) {
								queue.offer(i2);
							}
						}
					}
				}
			}
		}

		pacificSet.retainAll(atlanticSet);
		for (Integer idx : pacificSet) {
			int r = idx / n;
			int c = idx % n;
			result.add(Arrays.asList(r, c));
		}
		return result;
	}

}